/*
 * Copyright (C) 2010 Yury Kudryashov.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package name.kudryashov.collections.immutable;

import name.kudryashov.annotations.Immutable;
import name.kudryashov.base.Argument;
import name.kudryashov.collections.ExtArrays;
import name.kudryashov.collections.ExtCollections;
import name.kudryashov.collections.Iterators;
import name.kudryashov.collections.Lists;
import name.kudryashov.functions.Function2;

import java.util.AbstractCollection;
import java.util.Collection;
import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * Represents an immutable single-linked functional list.
 * <p>
 * Iterator returned by this list doesn't support the {@code remove}.
 * @param <E> element of the list
 */
@Immutable
public abstract class ListF<E> implements Iterable<E> {

    // TODO reduce*
    // TODO filter, partition
    // TODO zip, zipWithIndex
    // TODO sublist
    // TODO first, last, firstO, lastO
    // TODO map, flatMap 
    /**
     * Constructor for creating list from an array of elements.
     * @param elems elements
     * @param <E> type of element
     * @return new list instance
     */
    public static <E> ListF<E> list(E... elems) {
        return ExtArrays.foldRight(elems, new Nil<E>(), new Function2<E, ListF<E>, ListF<E>>() {
            public ListF<E> apply(E arg1, ListF<E> arg2) {
                return arg2.prepend(arg1);
            }
        });
    }

    /**
     * Constructor for creating list from any {@code Iterable}
     * @param elems elements, not null
     * @param <E> type of element
     * @return new list instance
     * @throws NullPointerException elems is null
     */
    public static <E> ListF<E> list(Iterable<E> elems) {
        Argument.requireNotNull(elems, "elems");
        return ExtCollections.foldRight(Lists.newArrayList(elems.iterator()), new Nil<E>(), new Function2<E, ListF<E>, ListF<E>>() {
            public ListF<E> apply(E arg1, ListF<E> arg2) {
                return arg2.prepend(arg1);
            }
        });
    }

    /**
     * @return true if this is a Nil (empty) list, false otherwise.
     */
    public abstract boolean isNil();

    /**
     * @return the head of the list
     * @throws NoSuchElementException this is an empty list
     */
    public abstract E head();

    /**
     * @return the tail of the list
     * @throws NoSuchElementException this is an empty list
     */
    public abstract ListF<E> tail();

    /**
     * Prepends a list with a given element.
     * @param arg element to prepend list with
     * @return a new list prepended with the given element
     */
    public ListF<E> prepend(E arg) {
        return new Cons<E>(arg, this);
    }

    /**
     * Prepends a list with a given list.
     * @param list to prepend this list with, not null
     * @return a new list prepended with the given element
     * @throws NullPointerException list is null
     */
    public ListF<E> prepend(ListF<? extends E> list) {
        Argument.requireNotNull(list, "list");
        ListF<E> prepended = this;
        for(E e : ExtCollections.reverse(list.toCollection())) {
            prepended = prepended.prepend(e);
        }
        return prepended;
    }

    /**
     * Converts this immutable list to a Java {@link Collection}.
     * @return a new collection backed up by this list.
     */
    public Collection<E> toCollection() {
        return new AbstractCollection<E>() {
            public Iterator<E> iterator() {
                return new ListFIterator<E>(ListF.this);
            }

            public int size() {
                return Iterators.size(iterator());
            }
        };
    }

    public Iterator<E> iterator() {
        return new ListFIterator<E>(this);
    }

    public ListFIterator<E> iteratorF() {
        return new ListFIterator<E>(this);
    }

    /**
     * @return true if this is a Nil (empty) list, false otherwise.
     */
    public abstract boolean isEmpty();

    /**
     * @return the size of this list. This operation is O(N).
     */
    public int size() {
        return foldLeft(0, new Function2<E, Integer, Integer>() {
            public Integer apply(E elem, Integer result) {
                return result + 1;
            }
        });
    }

    /**
     * Performs a left fold reduction of the list.
     * @param initial initial value
     * @param f folding function, not null
     * @param <R> type of the result
     * @return the folding result or initial value if the list is empty
     * @throws NullPointerException f is empty
     */
    public <R> R foldLeft(R initial, Function2<? super E, R, R> f) {
        R result = initial;
        for(ListF<E> list = this; !list.isEmpty(); list = list.tail()) {
            result = f.apply(list.head(), result);
        }
        return result;
    }

    /**
     * Performs a right fold reduction of the list. Does this recursively so a stack overflow may
     * occur on large lists.
     * <p>
     * For non-recursive implementation see {@link #foldRight}
     * @param initial initial value
     * @param f folding function, not null
     * @param <R> type of the result
     * @return the folding result or initial value if the list is empty
     * @throws NullPointerException f is empty
     */
    public <R> R foldRightR(R initial, Function2<? super E, R, R> f) {
        return iteratorF().foldRight(initial, f);
    }

    /**
     * Performs a right fold reduction of the list. Does this imperatively using a
     * separate stack instance so a stack overflow does not occur on large lists.
     * <p>
     * For recursive implementation see {@link #foldRightR}
     * @param initial initial value
     * @param f folding function, not null
     * @param <R> type of the result
     * @return the folding result or initial value if the list is empty
     * @throws NullPointerException f is empty
     */
    public <R> R foldRight(R initial, Function2<? super E, R, R> f) {
        return ExtCollections.foldRight(toCollection(), initial, f);
    }

    /**
     * @return this list as an array. The returned array is a copy, not a live view.
     */
    @SuppressWarnings({"unchecked"})
    public E[] toArray() {
        return (E[]) toCollection().toArray();
    }

    private static class Nil<E> extends ListF<E> {

        @Override
        public boolean isNil() {
            return true;
        }

        public boolean isEmpty() {
            return true;
        }

        public E head() {
            throw new NoSuchElementException("head");
        }

        public ListF<E> tail() {
            throw new NoSuchElementException("tail");
        }

        @Override
        public boolean equals(Object obj) {
            return obj.getClass() == Nil.class;
        }

        @Override
        public int hashCode() {
            return 196799; // some prime constant
        }
    }

    public static class Cons<E> extends ListF<E> {

        private final E head;
        private final ListF<E> tail;

        public Cons(E head, ListF<E> tail) {
            this.head = head;
            this.tail = Argument.requireNotNull(tail, "tail");
        }

        public boolean isNil() {
            return false;
        }

        @Override
        public E head() {
            return head;
        }

        @Override
        public ListF<E> tail() {
            return tail;
        }

        public boolean isEmpty() {
            return false;
        }

        @Override
        public boolean equals(Object o) {
            // easiest solution would be to implement this recursively but it may lead
            // to stack overflows on large lists, so use iteration.
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;


            ListF cons = (ListF) o;
            ListF list = this;
            while(!cons.isEmpty() && !list.isEmpty()) {
                Object consHead = cons.head();
                Object listHead = list.head();
                if (listHead != null ? !listHead.equals(consHead) : consHead != null) return false;
                cons = cons.tail();
                list = list.tail();
            }
            return cons.isEmpty() && list.isEmpty();
        }

        @Override
        public int hashCode() {
            // easiest solution would be to implement this recursively but it may lead
            // to stack overflows on large lists, so use iteration.
            int result = head != null ? head.hashCode() : 0;
            ListF list = tail();
            while(!list.isEmpty()) {
                Object listHead = list.head();
                result = 31 * result + (listHead != null ? listHead.hashCode() : 0);
                list = list.tail();
            }
            return result;
        }
    }

    public static class ListFIterator<E> implements Iterator<E> {
        private ListF<E> list;

        private ListFIterator(ListF<E> list) {
            this.list = list;
        }

        public boolean hasNext() {
            return !list.isEmpty();
        }

        public E next() {
            if(list.isEmpty()) {
                throw new NoSuchElementException();
            }
            E elem = list.head();
            list = list.tail();
            return elem;
        }

        public void remove() {
            throw new UnsupportedOperationException();
        }

        public <R> R foldLeft(R initial, Function2<? super E, R, R> f) {
            return Iterators.foldLeft(this, initial, f);
        }

        public <R> R foldRight(R initial, Function2<? super E, R, R> f) {
            if(hasNext()) {
                return f.apply(next(), foldRight(initial, f));
            }
            else {
                return initial;
            }
        }
    }
}